package 贪心;

/**
 * TODO
 *
 * @Description
 * @Author Lx
 * @Date 2024/7/21 1:52
 **/
public class 贪心8_加油站 {
    //1.暴力
    public int canCompleteCircuit_violence(int[] gas, int[] cost) {
        //1.遍历起点
        for (int i = 0; i < cost.length; i++) {
            int rest=gas[i]-cost[i];
            int index=(i+1)%cost.length;

            //有油且没走够一圈，才能继续走
            while(rest>0&&index!=i){
                rest+=(gas[index]-cost[index]);
                index=(index+1)%cost.length;
            }
            if(rest>=0&&index==i)return i;
        }
        return -1;
    }

    //2.贪心
    public int canCompleteCircuit(int[] gas, int[] cost) {
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(new 贪心8_加油站().canCompleteCircuit_violence(new int[]{1,2,3,4,5},new int[]{3,4,5,1,2}));
    }
}
